Parallel computation has become increasingly popular. Generally, a job may be divided into a plurality of task phases. The task at each phase may be dispatched to a plurality of different nodes so as to be executed in parallel. Then, the data generated at the preceding phase (called “intermediate data”) is passed to the task at the next phase for subsequent processing. There may be a plurality of tasks that can be executed in parallel during the same phase. For example, the MapReduce pattern is widely used in concurrent computation, wherein one job is divided into a Map phase and a Reduce phase. At the Map phase and Reduce phase, there may be a plurality of concurrently executable tasks, respectively. The intermediate result generated by the Map task is fed to the downstream Reduce task.
The phase of transmitting data between Map and Reduce may be called a scheduling phase or Shuffle. The scheduling phase is crucial for the overall performance of job execution. In some application scenarios, the execution time of the scheduling phase may amount to 90% of the total time of the Reduce task. In the traditional MapReduce pattern, the Map task and the Reduce task use different job slots, respectively. In order to improve the schedule, there has been proposed the architecture where the Map task and the Reduce task share a plurality of job slots. In this way, the utilization of resources such as a central processing unit (CPU), a network, and a disk of a node can be improved, and the time taken for the schedule can be reduced.
However, in such a MapReduce implementation, imbalance always occurs in the scheduling phase. When the data generation speed of the Map phase is lower than the data consuming speed of the Reduce phase, many reducers responsible for reducing might be in an idle or waiting state. On the contrary, when the speed of the Map phase is greater than the speed of the Reduce phase, the intermediate result generated by the mapper cannot be fetched in time. In order to solve this imbalance, a solution of controlling when to start the Reduce task using parameters has been proposed. Besides, a solution of controlling the schedule based on the ratio between the Map task and the Reduce task is also well-known. However, the parameters should be manually designed by human experts. Moreover, for different applications and different phases, the optimal parameters might be different. Therefore, the known parameter control cannot completely overcome the imbalance between the Map task and the Reduce task.
Specifically, it should be understood that the schedule issue between different phases of tasks are widely present in various parallel or distributive computations, not only limited to the MapReduce pattern as above depicted exemplarily. Generally, in parallel processing of a job, the mismatch of processing speeds between a task at the upstream phase (referred to as “upstream task”) and a task at the downstream phase (referred to as “downstream task”) will cause imbalance at the scheduling phase, thereby generating an adverse impact on the overall execution efficiency. For example, in parallel job processing in conformity with architectures such as MPI (Message Passing Interface), it is likely required to handle the potential imbalance between the upstream task and the downstream task.